#include<vector>
#include<algorithm>
using namespace std;
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //记录之前出现过最小的股价 和最大的利润即可
        int min_price=prices.front();
        int max_profit=0;
        for(auto e:prices){
            max_profit=max(e-min_price,max_profit);
            min_price=min(e,min_price);
        }
        return max_profit;
    }
};
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        //某一天 可以买 不买 卖?
        //某一天 只有两种状态 有股票 没有股票
        //每天都卖? 前面最低的时候买
        //dp[i]: 第i天的最大利润
        //dp[i]=max(dp[i-1],prices-min_price)
        vector<int>dp(prices.size(),0);
        dp[0]=0;
        int min_price=prices[0];
        for(int i=1;i<prices.size();i++){
            dp[i]=max(dp[i-1],prices[i]-min_price);
            min_price=min(min_price,prices[i]);
        }
        return dp.back();
    }
};